#include<string>
#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<algorithm>
using namespace std;

class Solution {
public:
	//vector<vector<string>> groupAnagrams(vector<string>& strs) {
	//	vector<vector<string>> results;
	//	unordered_map<unordered_set<char>,vector<string>> rules;
	//	for ( string str:strs) {
	//		unordered_set<char> rule;
	//		for(char ch : str) {
	//			rule.insert(ch);
	//		}
	//		auto it = rules.find(rule);
	//		if (it != rules.end()) {
	//			it->second.push_back(str);
	//		}
	//		else rules[rule].push_back(str);
	//	}
	//	return { {} };
	//}

	vector<vector<string>> groupAnagrams(vector<string>& strs) {
		if (strs.size() == 0) return { {} };
		unordered_map<int, vector<string>> rule2ans;
		vector<unordered_multiset<char>> rules;
		int index = 0;
		for (string str : strs) {
			unordered_multiset<char> rule;
			for (char ch : str) {
				rule.insert(ch);
			}
			bool founded = false;
			for (int i = 0; i < rules.size(); i++) {
				if(rules[i]==rule){
					rule2ans[i].push_back(str);
					founded = true;
					break;
				}
			}
			if (!founded) {
				rules.push_back(rule);
				rule2ans[index].push_back(str);
				index++;
			}
		}
		vector<vector<string>> result;
		for (auto it = rule2ans.begin(); it != rule2ans.end(); it++) {
			result.push_back(it->second);
		}
		return result;
	}

};

int main() {
	unordered_set<char> set;
	set.insert('e');
	set.insert('a');
	set.insert('t');
	unordered_set<char> set2;
	set2.insert('n');
	set2.insert('a');
	set2.insert('t');
	vector<unordered_set<char>> list;
	list.push_back(set);
	list.push_back(set2);
	unordered_set<char> set3;
	set3.insert('t');
	set3.insert('a');
	set3.insert('n');
	Solution s;
	vector<string> arr2 = { "ddddddddddg","dgggggggggg" };
	vector<string> arr = {"eat", "tea", "tan", "ate", "nat", "bat"};
	s.groupAnagrams(arr2);
	return 0;
}